package com.lw.leetcode.str.b;

/**
 * Created with IntelliJ IDEA.
 * 2156. 查找给定哈希值的子串
 *
 * @author liw
 * @version 1.0
 * @date 2022/2/8 17:27
 */
public class SubStrHash {

    public static void main(String[] args) {
        SubStrHash test = new SubStrHash();

        // 1 <= k <= s.length <= 2 * 104
        //1 <= power, modulo <= 109
        //0 <= hashValue < modulo
        //s 只包含小写英文字母。
        //测试数据保证一定 存在 满足条件的子串。。

        // "ee"
//        String s = "leetcode";
//        int power = 7;
//        int modulo = 20;
//        int k = 2;
//        int hashValue = 0;

        // "fbx"
//        String s = "fbxzaad";
//        int power = 31;
//        int modulo = 100;
//        int k = 3;
//        int hashValue = 32;

        // "xxterzixjqrghqyeketqeynekvqhc"
        //15
        //94
        //4
        //16

        // nekv
        String s = "xxterzixjqrghqyeketqeynekvqhc";
        int power = 15;
        int modulo = 94;
        int k = 4;
        int hashValue = 16;

        String s1 = test.subStrHash(s, power, modulo, k, hashValue);
        System.out.println(s1);

    }

    public String subStrHash(String s, int power, int modulo, int k, int hashValue) {
        char[] arr = s.toCharArray();
        int length = arr.length;
        long item = 0L;
        long it = 1L;
        int i = length - k;
        int st = i;
        for (; i < length; i++) {
            item = (item + (arr[i] - 96) * it) % modulo;
            it = it * power % modulo;
        }
        i = length - k - 1;
        while (i != -1) {
            item = ((item * power - it * (arr[i + k] - 96)) % modulo + modulo + arr[i] - 96) % modulo;
            if (item == hashValue) {
                st = i;
            }
            i--;
        }
        return s.substring(st, st + k);
    }


}
